package com.kang.c0c.tree;

import java.util.Vector;

import com.kang.c0c.symbol.FunctionSymbol;
import com.kang.c0c.tree.node.BinaryNode;
import com.kang.c0c.tree.node.BlockNode;
import com.kang.c0c.tree.node.CallNode;
import com.kang.c0c.tree.node.EvaluateNode;
import com.kang.c0c.tree.node.FunctionNode;
import com.kang.c0c.tree.node.IfNode;
import com.kang.c0c.tree.node.LeafNode;
import com.kang.c0c.tree.node.Node;
import com.kang.c0c.tree.node.Nodes;
import com.kang.c0c.tree.node.PrintNode;
import com.kang.c0c.tree.node.ReturnNode;
import com.kang.c0c.tree.node.ScanNode;
import com.kang.c0c.tree.node.SimpleBlock;
import com.kang.c0c.tree.node.WhileNode;
import com.kang.c0c.util.Context;
import com.kang.c0c.util.Log;

public class TreeDivSimpleBlock {	
	private Tree tree;
	private Log log;
	
	public TreeDivSimpleBlock(Context context){
		super();
		tree = Tree.instance(context);
		log = Log.instance(context);
	}
	
	private SimpleBlock IfDAG(BlockNode father, BlockNode subBlock,
			SimpleBlock simple, IfNode check, boolean isInt){
		Node cond = DAG(simple,check.getCondition());
		BinaryNode condLeaf = new BinaryNode(Nodes.IF, cond, null);
		
		/*
		 * 判断条件是否永真或者永假，如果是，则剔除这个控制流的基本块
		 */
		if(cond instanceof LeafNode){
			int control = (Integer)((LeafNode)cond).getValue();
			
			if(control == 1){
				if(check.getExecBlock() != null)
					subBlock.insertAt(check.getExecBlock(), 1);
			}else{
				if(check.getElseBlock() != null)
					subBlock.insertAt(check.getElseBlock(), 1);
			}
			
			return simple;
		}
		
		SimpleBlock left = null;
		SimpleBlock right = null;
		boolean leftRet = false;
		boolean rightRet = false;
		
		if(check.getExecBlock() != null){
			left = new SimpleBlock(simple);
			leftRet = subBlock(father,check.getExecBlock(),isInt,left);
			if(left.binarySize() == 0)
				left = null;
		}
		
		if(check.getElseBlock() != null){
			right = new SimpleBlock(simple);
			rightRet = subBlock(father,check.getElseBlock(),isInt,right);
			if(right.binarySize() == 0)
				right = null;
		}
		
		if((left != null)||(right != null)){
			BinaryNode binary = new BinaryNode(Nodes.IF, left, right);
			condLeaf.setRight(binary);
			
			int condIndex = simple.insertBinary(condLeaf);
			simple.getBinary(condIndex).incUse();
			
			if(leftRet && rightRet)
				return null;
			
			if(subBlock.size() > 1){
				SimpleBlock next;
				/*
				 * 初始化从上一个基本块得到的Value哈希表
				 */
				if((left!=null)&&(right!=null)){
					next = new SimpleBlock(left);
					next.unionValue(right);
				}else if(left!=null){
					next = new SimpleBlock(simple);
					next.unionValue(left);
				}else{
					next = new SimpleBlock(simple);
					next.unionValue(right);
				}
				
				simple.next = next;
				next.prev = simple;
				simple = next;
				father.insertNode(simple);
			}
		}
		return simple;
	}
	
	private SimpleBlock WhileDAG(BlockNode father, BlockNode subBlock,
			SimpleBlock simple, WhileNode loop, boolean isInt){
		
		SimpleBlock conBlock = new SimpleBlock();
		BinaryNode conLeaf = new BinaryNode(Nodes.WHILE);
		int condIndex = conBlock.insertBinary(conLeaf);
		conBlock.getBinary(condIndex).incUse();
		
		Node cond = DAG(conBlock,loop.getCondition());
		conLeaf.setLeft(cond);
		cond.incUse();
		father.insertNode(conBlock);
		
		SimpleBlock execBlock = null;
		if(loop.getExecBlock() != null){
			execBlock = new SimpleBlock();
			subBlock(father,loop.getExecBlock(),isInt,execBlock);
			if(execBlock.binarySize() == 0)
				execBlock = null;
			conLeaf.setRight(execBlock);
		}
				
		simple.next = conBlock;
		conBlock.prev = simple;
		
		if(subBlock.size() > 1){
			simple =  new SimpleBlock();
			conBlock.next = simple;
			simple.prev = conBlock;
			father.insertNode(simple);
		}
		return simple;
	}
	
	private void EvaDAG(SimpleBlock simple, BinaryNode binary){
		LeafNode left = (LeafNode)binary.getLeft();
		
		if(left.getNode() != Nodes.VAR){
			System.err.println("Error:TreeDivSimpleBlock.EvaDAG()");
			System.exit(-1);
		}
		
		Node right = DAG(simple, (BinaryNode)binary.getRight());
		simple.insertEva(left,right);		
	}
	
	private Node CallDAG(SimpleBlock simple, CallNode call){
		int t = call.getParamCount()-1;
		BinaryNode binary, paramNode;
		Node param;
		Vector<BinaryNode> params = new Vector<BinaryNode>();
		
		while(t >= 0){
			binary = call.NodeAt(t);
			param = DAG(simple,binary);
			paramNode = new BinaryNode(Nodes.PARAM,param,null);
			params.add(paramNode);			
			t--;
		}
		
		while(params.size() > 0){
			int i = simple.insertBinary(params.elementAt(0));
			simple.getBinary(i).incUse();
			params.remove(0);
		}
		
		LeafNode leaf = new LeafNode(Nodes.VAR, call.getFuncSym());
		BinaryNode node = new BinaryNode(Nodes.CALL, leaf, null);
		int index = simple.insertBinary(node);
		simple.getBinary(index).incUse();
		
		return simple.getBinary(index);
	}
	
	private void ScanDAG(SimpleBlock simple, ScanNode scan){
		LeafNode varIdent = scan.getVarIdent();
		BinaryNode node;
		int scanIndex;
		
		simple.insertUnary(varIdent);
		node  = new BinaryNode(Nodes.SCAN, varIdent, null);
		scanIndex = simple.insertBinary(node);
		simple.getBinary(scanIndex).incUse();
		simple.updateValue(varIdent, null);
	}
	
	private void PrintDAG(SimpleBlock simple, PrintNode print){
		LeafNode leaf = null;
		Node expr = null;
		
		if(print.getStr() != null){
			int leafIndex = simple.lookForUnary(print.getStr());
			leaf= simple.getUnary(leafIndex);
		}
		
		if(print.getExpr() != null){			
			expr = DAG(simple, print.getExpr());
		}
		
		BinaryNode node = new BinaryNode(Nodes.PRINT, leaf, expr);
		int index = simple.insertBinary(node);
		simple.getBinary(index).incUse();
	}
	
	private void ReturnDAG(SimpleBlock simple, ReturnNode retNode, boolean isInt){
		if(isInt){
			if(retNode.getExpr() == null){
				log.error(retNode.getPos(), "Type Mistake: 'void' illegal with all types");
				retNode.setExpr(new BinaryNode(Nodes.UNARY,new LeafNode(Nodes.NUM,0), null));
			}
			
			Node sub = DAG(simple,retNode.getExpr());
			BinaryNode node = new BinaryNode(Nodes.RETURN, sub, null);
			int index = simple.insertBinary(node);
			simple.getBinary(index).incUse();
			
		}else{
			if(retNode.getExpr() != null){
				log.error(retNode.getPos(), "Type Mistake: 'int' illegal with 'void' function");
			}
			
			BinaryNode node = new BinaryNode(Nodes.RETURN, null, null);
			int index = simple.insertBinary(node);			
			simple.getBinary(index).incUse();
		}
	}
	
	/**
	 * 
	 * @param simple
	 * @param left
	 * @param right
	 * @param nodeKind
	 * @return
	 */
	private LeafNode genValueNode(SimpleBlock simple,
			int left, int right , int nodeKind){
		LeafNode leaf = new LeafNode();
		leaf.setNode(Nodes.NUM);
		
		switch(nodeKind){
		case Nodes.PLU:
			leaf.setValue(left+right);
			break;
		case Nodes.SUB:
			leaf.setValue(left-right);
			break;
		case Nodes.MUL:
			leaf.setValue(left*right);
			break;
		case Nodes.DIV://不能防止整数不能局部整除的情况，即1/3×6=0，而不是1/3×6=2，虽然后者才是正确的！
			leaf.setValue(left/right);
			break;
		case Nodes.EQU:
			if(left==right)
				leaf.setValue(1);
			else
				leaf.setValue(0);
			break;
		case Nodes.NEQ:
			if(left!=right)
				leaf.setValue(1);
			else
				leaf.setValue(0);
			break;
		case Nodes.GT:
			if(left>right)
				leaf.setValue(1);
			else
				leaf.setValue(0);
			break;
		case Nodes.GEQ:
			if(left>=right)
				leaf.setValue(1);
			else
				leaf.setValue(0);
			break;
		case Nodes.LT:
			if(left<right)
				leaf.setValue(1);
			else
				leaf.setValue(0);
			break;
		case Nodes.LEQ:
			if(left<=right)
				leaf.setValue(1);
			else
				leaf.setValue(0);
			break;
		default:
			log.error(0, "TreeOptimize.mergeLeafNode() failed!");
			break;
		}
		
		return simple.getUnary(simple.lookForUnary(leaf));
	}
	
	/**
	 * 
	 * @param simple
	 * @param left
	 * @param right
	 * @param nodeKind
	 * @return
	 */
	private Node mergeLeafNode(SimpleBlock simple, 
			LeafNode left, LeafNode right, int nodeKind){
		int leftIndex = simple.lookForUnary(left);
		int rightIndex = simple.lookForUnary(right);
		Integer leftI = simple.getValue(leftIndex);
		Integer rightI = simple.getValue(rightIndex);
		
		if((leftI!=null)&&(rightI!=null)){
			if(nodeKind == Nodes.DIV){
				
				int answer = leftI / rightI;
				if(answer*rightI == leftI){
					LeafNode leaf = new LeafNode(Nodes.NUM,answer);
					return simple.getUnary(simple.lookForUnary(leaf));
				}
			}else
				return genValueNode(simple,leftI,rightI,nodeKind);
		}
		
		BinaryNode binary = new BinaryNode(nodeKind,left,right);
		int index = simple.lookForBinary(binary);
		
		return simple.getBinary(index);			
	}
	
	private Node mergeNode(SimpleBlock simple, Node left, Node right, int nodeKind){
		if((left instanceof LeafNode)
				&&(right instanceof LeafNode)){			
			return mergeLeafNode(simple, (LeafNode)left, (LeafNode)right, nodeKind);
		}else{
			/*
			 * PLU,MUL,SUB,DIV的跨节点合并，如：
			 * x = (a+5) + (b-6);
			 * 按照常理可以合并成 x= a+b-1;
			 * 但是a+5为左节点b-6为右节点，分析后就无法进行合并
			 * 
			 * 没有什么实际效果，所以没有意义！不做！
			 */
			BinaryNode binary = new BinaryNode(nodeKind,left,right);
			int index = simple.lookForBinary(binary);
			
			return simple.getBinary(index);
		}
	}
	
	private Node DAG(SimpleBlock simple, BinaryNode binary){
		if(binary.getNode() == Nodes.UNARY){
			Node node = binary.getLeft();
			if(node.getNode() == Nodes.CALL)
				return CallDAG(simple,(CallNode)node);
			else{
				LeafNode leaf = (LeafNode)binary.getLeft();
				int index = simple.lookForUnary(leaf);
				
				return simple.getUnary(index);
			}
		}else{
			Node left = DAG(simple, (BinaryNode)binary.getLeft());
			Node right = DAG(simple, (BinaryNode)binary.getRight());
			
			return mergeNode(simple,left,right,binary.getNode());
		}
	}
	
	private boolean subBlock(BlockNode father, BlockNode subBlock,
			boolean isInt, SimpleBlock simple){		
		father.insertNode(simple);
		
		while(subBlock.size() > 0){
			Node subNode = subBlock.get(0);

			if(subNode instanceof IfNode){
				
				simple = IfDAG(father, subBlock, simple, (IfNode)subNode, isInt);
				
				if(simple == null)
					return true;
				
			}else if(subNode instanceof WhileNode){
								
				simple = WhileDAG(father, subBlock, simple, (WhileNode)subNode, isInt);
				
			}else if(subNode instanceof BlockNode){
				
				BlockNode newBlock = (BlockNode)subNode;
				int t = 0;
				while(t < newBlock.size()){
					subBlock.insertAt(newBlock.get(t), t+1);
					t++;
				}
				
			}else if(subNode instanceof CallNode){
				
				CallDAG(simple, (CallNode)subNode);
				
			}else if(subNode instanceof EvaluateNode){
				
				EvaluateNode eval = (EvaluateNode) subNode;
				BinaryNode binary = new BinaryNode(Nodes.EVA, eval.getIdent(), eval.getExpr());
				EvaDAG(simple,binary);
				
			}else if(subNode instanceof ReturnNode){
				
				ReturnDAG(simple, (ReturnNode)subNode, isInt);
				return true;
				
			}else if(subNode instanceof ScanNode){
				
				ScanDAG(simple,(ScanNode)subNode);				
				
			}else if(subNode instanceof PrintNode){
				
				PrintDAG(simple, (PrintNode)subNode);
				
			}else{
				System.err.println("Error:TreeDivSimpleBlock.divBlock(): Unexpected sub node in block");
				System.exit(-1);
			}
			
			subBlock.removeNode(0);
		}
		
		return false;
	}
	
	private void divFunctionBlock(FunctionNode funcNode){
		BlockNode block = funcNode.getBlock();
		BlockNode newBlock = new BlockNode();
		boolean isInt = FunctionSymbol.isInt(funcNode.getSym());
		boolean isRet;

		isRet = subBlock(newBlock, block, isInt, new SimpleBlock());
		
		if(isInt && !isRet){
			log.error(0, "A value is required to return for function " +funcNode.getSym().getName());
		}
		
		int i = 0;
		while(i<newBlock.size()){
			Node node = newBlock.get(i);
			if(node instanceof SimpleBlock){
				SimpleBlock simple = (SimpleBlock)node;
				simple.cleanBlock();
				
				if(simple.binarySize() == 0){
					if(simple.prev != null){
						simple.prev.next = simple.next;
					}else if(simple.next != null){
						SimpleBlock temp = simple.next;
						if(! temp.equals(newBlock.get(i+1))){
							
						}

						newBlock.removeNode(i);
						newBlock.insertAt(temp, i);
					}
					
					newBlock.removeNode(i);
				}
				else
					i++;
			}else{
				newBlock.removeNode(i);
			}
		}
		
		funcNode.setBlock(newBlock);
	}
	
	public void divBlock(){
		int i = 0;
		while(i < tree.size()){
			divFunctionBlock(tree.getByName(tree.getFunctionName(i)));
			i++;
		}
	}
}
